Processors typically use a cache to improve performance and decrease system costs. Caches temporarily store recently accessed information (blocks of instructions or data) in a memory that is typically smaller and faster to access than a larger main memory. Caches are effective because a block that has been accessed once is likely to be accessed again in the near future or is often near a recently accessed block. Thus, as a task executes, the working set of a task (the instructions and data currently required for the task) is stored in the cache in the event that the information may be accessed again. A cache typically maps multiple blocks of information from the main memory into one place in a cache, typically referred to as a “set.” A “block” refers to the minimum unit of information that can be present in a cache and a “frame” is the place in a cache where a single block may be stored. In a set associative cache, multiple frames are grouped into sets. For example, a two-way set associative cache has two frames in each set.
In many embedded applications, a primary task may be interrupted by one or more secondary tasks. Thus, following an interruption, as a secondary, interrupting task executes, the working set of the interrupting task is stored in the cache, potentially evicting the working set of the primary, interrupted task and thereby decreasing the performance of the primary task when it resumes execution. When the primary task resumes execution, portions of the working set that have been evicted from the cache must be obtained from main memory, causing a “cache miss.” Thus, the execution time of the primary task is extended by the time taken to run the secondary task plus the miss penalty caused by obtaining evicted portions of the cached information from the main memory.
A number of techniques have been proposed or suggested for improving the performance of caches that are used with embedded processors. Cache frame locking, for example, is a technique that prevents the contents of specified cache frames from being evicted. In this technique, a specified group of frames is “locked” and the blocks they contain may not be evicted until they are unlocked. A block in a locked frame may be read or written by any task. A frame's invalidation causes the frame to be unlocked. Locking and unlocking may be exercised by the execution of a special instruction or by writing to a memory-mapped control register that may control groups of frames or individual frames. The locking of some of an executing task's frames prior to another task's execution ensures that blocks in those frames are not evicted. This may enhance the performance of the interrupted task when it resumes execution.
While conventional cache frame locking techniques have significantly improved cache performance in embedded processor systems, they suffer from a number of limitations, which if overcome, could further improve the performance of cache memories. Specifically, conventional cache frame locking techniques are not practical unless the frames in use by a task are known in advance, otherwise unnecessary frames may be locked, or frames key to efficient execution of the task may not be locked. In addition, locking unnecessary frames decreases the cache space that is available to an interrupting task, which may decrease performance of the interrupting task unnecessarily. However, knowledge of the frame use by a task is difficult to obtain because the specific frames that a task may access usually vary widely over time and often in a manner that cannot be anticipated. Even if a task's frame use over time is known, it may be of little value if an interrupting task may begin execution at an indeterminate point in time, which is often the case.
A need therefore exists for a cache frame locking technique that automatically identifies appropriate frames to lock at any given time. More specifically, a need exists for a cache frame locking mechanism that identifies frames that are likely to be accessed by a task in the near future. Yet another need exists for a cache frame locking technique that adapts to the frame use of a particular task. In addition, a need exists for a mechanism that automatically unlocks frames that cause significant performance degradation for a running task.